from sys import stdin
import heapq
def trace_path(i, j, visited, grid):
while j != 0:
grid[i][j] = '#'
i, j = visited[i][j]
grid[i][j] = '#'
for r in grid:
print("".join(r))
def solve():
n, m = map(int, stdin.readline().split())
grid = [list(stdin.readline().strip()) for i in range(n)]
visited = [[None] * m for i in range(n)]
for i in range(n):
for j in range(m):
if grid[i][j] == '#':
for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
if 0 <= i + di < n and 0 <= j + dj < m:
visited[i+di][j+dj] = -1
q = [(1 if grid[i][0] == '.' else 0, i, 0) for i in range(n) if visited[i][0] != -1]
heapq.heapify(q)
while q:
c, i, j = heapq.heappop(q)
if j == m - 1:
print("YES")
trace_path(i, j, visited, grid)
return
for di, dj in ((-1, -1), (-1, 1), (1, -1), (1, 1)):
if 0 <= i + di < n and 0 <= j + dj < m \
and not visited[i+di][j+dj]:
visited[i+di][j+dj] = (i,j)
heapq.heappush(q, (c + (grid[i+di][j+dj] == '.'), i+di, j+dj))
print("NO")
for _ in range(int(stdin.readline())):
solve()#include <bits/stdc++.h>
using namespace std;
const long long MX=2e5+10;
const long long INF=1e18;
vector < long long > blc[MX];
vector < pair < long long , long long > > shl[MX];
vector < string > mas(MX);
long long corx[4]={1,1,-1,-1};
long long cory[4]={-1,1,1,-1};
priority_queue < pair < long long , pair < long long , long long > > > q;
long long n,m;
void BFS()
{
while(!q.empty())
{
long long zarx=q.top().second.first;
long long zary=q.top().second.second;
q.pop();
for(long long i=0;i<4;i++)
{
if(blc[zarx+corx[i]][zary+cory[i]]==-1)
{
continue;
}
if(blc[zarx+corx[i]][zary+cory[i]]==0 || (blc[zarx][zary]+(mas[zarx+corx[i]][zary+cory[i]]=='.'))<blc[zarx+corx[i]][zary+cory[i]])
{
blc[zarx+corx[i]][zary+cory[i]]=(blc[zarx][zary]+(mas[zarx+corx[i]][zary+cory[i]]=='.'));
shl[zarx+corx[i]][zary+cory[i]]=make_pair(zarx,zary);
q.push({-blc[zarx+corx[i]][zary+cory[i]],{zarx+corx[i],zary+cory[i]}});
}
}
}
return;
}
void fl()
{
for(long long i=0;i<=n+1;i++)
{
blc[i].resize(m+5);
shl[i].resize(m+5);
fill(blc[i].begin(),blc[i].end(),0);
fill(shl[i].begin(),shl[i].end(),make_pair(0,0));
blc[i][0]=-1;
blc[i][m+1]=-1;
}
fill(blc[0].begin(),blc[0].end(),-1);
fill(blc[n+1].begin(),blc[n+1].end(),-1);
return;
}
void fndshl()
{
long long zarx,zary;
long long abab=INF;
for(long long i=1;i<=n;i++)
{
if(blc[i][m]>0 && blc[i][m]<abab)
{
abab=blc[i][m];
zarx=i;
zary=m;
}
}
queue < pair < long long , long long > > nz;
while(zary!=1)
{
nz.push({zarx,zary});
long long newzarx=shl[zarx][zary].first;
long long newzary=shl[zarx][zary].second;
zarx=newzarx;
zary=newzary;
}
nz.push({zarx,zary});
while(!nz.empty())
{
mas[nz.front().first][nz.front().second]='#';
nz.pop();
}
cout<<"YES\n";
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=m;j++)
{
cout<<mas[i][j];
}
cout<<"\n";
}
return;
}
long long vipch()
{
fl();
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=m;j++)
{
if(((i+j)%2)==1 && mas[i][j]=='#')
{
blc[i-1][j]=-1;
blc[i][j-1]=-1;
blc[i+1][j]=-1;
blc[i][j+1]=-1;
}
}
}
for(long long i=1;i<=n;i+=2)
{
if(blc[i][1]==0)
{
blc[i][1]=1+(mas[i][1]=='.');
q.push({-blc[i][1],{i,1}});
}
}
BFS();
long long rt=INF;
for(long long i=1;i<=n;i++)
{
if(blc[i][m]>0)
{
rt=min(rt,blc[i][m]);
}
}
return rt;
}
long long vipb()
{
fl();
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=m;j++)
{
if(((i+j)%2)==0 && mas[i][j]=='#')
{
blc[i-1][j]=-1;
blc[i][j-1]=-1;
blc[i+1][j]=-1;
blc[i][j+1]=-1;
}
}
}
for(long long i=2;i<=n;i+=2)
{
if(blc[i][1]==0)
{
blc[i][1]=1+(mas[i][1]=='.');
q.push({-blc[i][1],{i,1}});
}
}
BFS();
long long rt=INF;
for(long long i=1;i<=n;i++)
{
if(blc[i][m]>0)
{
rt=min(rt,blc[i][m]);
}
}
return rt;
}
void fun()
{
cin>>n>>m;
string s;
for(long long i=1;i<=n;i++)
{
cin>>s;
s="&"+s+"&";
mas[i]=s;
}
long long mxansch=vipch();
long long mxansb=vipb();
//cout<<mxansch<<" "<<mxansb<<"\n";
if(mxansb==INF && mxansch==INF)
{
cout<<"NO\n";
return;
}
if(mxansch<mxansb)
{
vipch();
fndshl();
}
else
{
vipb();
fndshl();
}
return;
}
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
long long t;
cin>>t;
while(t--)
{
fun();
}
return 0;
}
957. Prison Cells After N Days | 946. Validate Stack Sequences |
921. Minimum Add to Make Parentheses Valid | 881. Boats to Save People |
497. Random Point in Non-overlapping Rectangles | 528. Random Pick with Weight |
470. Implement Rand10() Using Rand7() | 866. Prime Palindrome |
1516A - Tit for Tat | 622. Design Circular Queue |
814. Binary Tree Pruning | 791. Custom Sort String |
787. Cheapest Flights Within K Stops | 779. K-th Symbol in Grammar |
701. Insert into a Binary Search Tree | 429. N-ary Tree Level Order Traversal |
739. Daily Temperatures | 647. Palindromic Substrings |
583. Delete Operation for Two Strings | 518. Coin Change 2 |
516. Longest Palindromic Subsequence | 468. Validate IP Address |
450. Delete Node in a BST | 445. Add Two Numbers II |
442. Find All Duplicates in an Array | 437. Path Sum III |
436. Find Right Interval | 435. Non-overlapping Intervals |
406. Queue Reconstruction by Height | 380. Insert Delete GetRandom O(1) |